//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 
//
// 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [0,1,0,3,12]
//输出: [1,3,12,0,0]
// 
//
// 示例 2: 
//
// 
//输入: nums = [0]
//输出: [0] 
//
// 
//
// 提示: 
// 
//
// 
// 1 <= nums.length <= 10⁴ 
// -2³¹ <= nums[i] <= 2³¹ - 1 
// 
//
// 
//
// 进阶：你能尽量减少完成的操作次数吗？ 
// Related Topics 数组 双指针 👍 1599 👎 0


import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution0283 {
    /**
     * [283]移动零 筛选有用的,覆盖没用的-双指针
     * <p>
     * 时间复杂度:O(n)
     * <br>
     * 空间复杂度:O(1)
     */
    public void moveZeroes(int[] nums) {
        int index = 0; // space 1
        for (int num : nums) { // time n
            if (num != 0) {
                nums[index++] = num;
            }
        }
        for (; index < nums.length; index++) { // time index
            nums[index] = 0;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

class Test0283 {
    public static void main(String[] args) {
        int[] nums1 = {0, 1, 0, 3, 12};
        int[] nums2 = {0};
        int[] nums3 = {2, 1};
        int[] nums4 = {1, 0, 1};

        show(Arrays.asList(nums1, nums2, nums3, nums4));
    }

    private static void show(List<int[]> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.println("\n----" + i + "----");
            firstOptimization3(list.get(i));
            System.out.println("->" + Arrays.toString(list.get(i)));
        }
    }

    public static void first(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int n = nums.length;

        // 0 1 0 3 12
        // 1 3 12 0 0
        int slow = 0;
        int fast = 0;

        while (fast < n) {
            // 如果快指针为 0
            if (nums[fast] == 0) {
                fast++;
            }
            // 如果快指针不是 0
            else {
                // 慢指针为 0, 交换快慢指针
                if (nums[slow] == 0) {
                    nums[slow] ^= nums[fast];
                    nums[fast] ^= nums[slow];
                    nums[slow] ^= nums[fast];
                    slow++;
                    fast++;
                }
                // 慢指针不是 0
                else {
                    slow++;
                    fast++;
                }
            }
        }
    }

    public static void firstOptimization(int[] nums) {
        int slow = 0;
        int fast = 0;

        while (fast < nums.length) {
            // 如果快指针不为 0
            if (nums[fast] != 0) {
                // 慢指针为 0, 交换快慢指针
                if (nums[slow] == 0) {
                    nums[slow] ^= nums[fast];
                    nums[fast] ^= nums[slow];
                    nums[slow] ^= nums[fast];
                }
                slow++;
            }
            fast++;
        }
    }

    /**
     * 双指针 异或交换
     * <p>
     * 时间复杂度:O(n)
     * <br>
     * 空间复杂度:O(1)
     */
    public static void firstOptimization2(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) { // time n
            // 如果快指针不为 0
            if (nums[fast] != 0) {
                // 慢指针为 0, 交换快慢指针
                if (nums[slow] == 0) {
                    nums[slow] ^= nums[fast];
                    nums[fast] ^= nums[slow];
                    nums[slow] ^= nums[fast];
                }
                slow++;
            }
        }
    }

    /**
     * 双指针 额外空间交换(与异或交换没有性能差异)
     * <p>
     * 时间复杂度:O(n)
     * <br>
     * 空间复杂度:O(1)
     */
    public static void firstOptimization3(int[] nums) {
        int slow = 0;
        int temp;
        for (int fast = 0; fast < nums.length; fast++) { // time n
            // 如果快指针不为 0
            if (nums[fast] != 0) {
                // 慢指针为 0, 交换快慢指针
                if (nums[slow] == 0) {
                    temp = nums[fast];
                    nums[fast] = nums[slow];
                    nums[slow] = temp;
                }
                slow++;
            }
        }
    }

    /**
     * 筛选有用的, 覆盖没用的
     * <p>
     * 时间复杂度:O(n)
     * <br>
     * 空间复杂度:O(1)
     */
    public static void moveZeroes(int[] nums) {
        int index = 0; // space 1
        for (int num : nums) { // time n
            if (num != 0) {
                nums[index++] = num;
            }
        }
        for (; index < nums.length; index++) { // time index
            nums[index] = 0;
        }
    }

}
